In our International patent application WO-A-98/27694, the entire disclosure of which is incorporated herein by reference, there is disclosed a communications apparatus comprising a network in the form of a “mesh” of interconnected nodes. Each node in the mesh can communicate with plural other nodes via individual respective point-to-point radio links between nodes by means of substantially unidirectional (i.e. highly directional) radio transmissions along the links, i.e. signals are not broadcast but are instead directed to a particular node with signals being capable of being passed in both directions along the link. The frequency used may be for example at least about 1 GHz. A frequency greater than 2.4 GHz or 4 GHz may be used. Indeed, a frequency of 40 GHz, 60 GHz or even 200 GHz may be used. Beyond radio frequencies, other yet higher frequencies such as of the order of 100,000 GHz (infra-red) could be used. In the preferred embodiment, each node in the mesh has plural antennas which provide plural potential point-to-point transmission links to other nodes. For example, each node may have four or eight antennas each respectively providing a link to another node. (It will be understood that in this context, “antenna” is to be construed broadly and includes any arrangement that can send or receive a highly directional beam. The plural antennas may for example be provided by plural physically discrete antennas that are individually selectable, by one or more physically steerable antennas, or by a phased array antenna.) In an example, time division duplex (TDD) is used to alternate transmission and reception at the nodes by dividing transmission and reception time frames into discrete timeslots.
The primary advantages of this “mesh” approach are set out in WO-A-98/27694 and include the distribution of bandwidth across the mesh and its associated capacity advantages over alternative systems (such as point-to-multipoint or broadcast systems); the availability of diverse traffic paths to at least the majority of nodes, which potentially allows service to be maintained regardless of whether or not a particular node has failed, thereby giving high resilience; and the potential to supply different nodes with widely varying levels of data traffic without the need for more than one type of radio link, simply by using a variable number of data paths to carry the data traffic. A wireless system has obvious advantages over a wired system in that it is not necessary to dig up roads, etc. to lay and maintain cables.
At least some and more preferably most nodes in the fully established mesh of interconnected nodes will be associated with a subscriber, which may be a natural person or an organisation such as a company, university, etc. Each subscriber node will typically act as the end point of a link dedicated to that subscriber (i.e. as a source and as a sink of data traffic) and also as an integral part of the distribution network for carrying data intended for other nodes. However, an operator of the mesh network may initially deploy a set of “seed” nodes in a “seed network”. A seed node will typically be a non-subscriber node (though it may later be converted into a subscriber node) that is placed by the network operator prior to offering network services to potential subscribers and will typically be deployed to be highly visible to a large number of potential subscribers. (The word “visible” and the phrase “line-of-sight” or similar will be used herein in the sense that when two nodes or sites are said to be “visible” to each other or to be in “line-of-sight” with each other, the nodes or nodes positioned at the sites can in principle communicate with each other wirelessly at the frequency or frequencies used in the network when suitable transmitting and receiving equipment is installed at the site.) In the seed network, each node is visible to at least one other node. The seed network allows a suitable, minimum number of subscriber nodes to be connected to the mesh directly via these seed nodes when network services are offered by the operator. The seed nodes will typically act only as transit nodes and not as either sources or sinks of network traffic (whether for example user traffic or network management traffic). A seed node may in due course be associated with a subscriber and therefore become a subscriber node.
Formation
Once there has been established a suitable seed network or other set of nodes in which each node is in principle visible to at least one other node, it is necessary to select from all possible lines-of-sight between the nodes (i.e. potential wireless transmission links between the nodes) those which are most suitable for use as actual wireless transmission links between the nodes. This process will be referred to herein by the phrase “formation of a mesh” or similar. It will be understood that the process of formation of a mesh can be used for any mesh and may for example be used during initial formation of a mesh and during growth of a mesh, and may be applied repeatedly. It should be borne in mind that the problem of formation of a mesh of interconnected nodes of the type disclosed in WO-A-98/27694 and discussed above is a problem that does not arise in other network systems. For example, in a conventional telephone network or in for example the Internet, there already exists a network in which links exist between subscribers; network issues in such networks tend only to be concerned with the problem of routing from one subscriber to another in the existing network, taking into account the fact that some links may be faulty or otherwise unavailable. In contrast, given a set of nodes which are to be connected to form a mesh of interconnected nodes as disclosed in our WO-A-98/27694 and discussed above, typically the communication links for any one node can be set up to link that node to one (or other predetermined number) of many other nodes. In other words, there are many choices of ways of linking the nodes to provide a mesh. Therefore, one of the first problems to be addressed is how to form the mesh of interconnected nodes, i.e. given a set of nodes, how to determine which nodes should be provided with communication links to which other nodes. Such links should preferably be chosen such that these links provide adequate capacity for all data traffic to be routed across these links.
The problem of mesh formation will normally be a mathematically hard problem given the enormous number of potential links that will exist given a typical set of (unconnected) nodes and the fact that the number of combinations of potential communication links increases much more rapidly than the number of nodes. Moreover, not all topologically valid meshes will be suitable for use as a mesh network because of practical problems, such as for example the presence of a limited number of antennas available at each node, data traffic capacity limitations at each node or of the available RF spectrum (including a limitation on the number of timeslots available for transmission and reception), and restrictions on the length of traffic paths between the nodes (measured both in physical lengths of individual links and the number of transit nodes through which data passes from a source node to a target node).
In one implementation of the mesh, the mesh will be a self-contained or “non-access” network, that is the network is not connected to any external network. Such a non-access network is useful for example as a local area network or a wide area network, which may for example be used by a single organisation to provide network services to its users.
In the preferred implementation however, the mesh will typically be connected to an external network. For example, where the mesh is an access network, the external network will be a core network such as a trunk network. The point at which traffic passes from the external network into the mesh and vice versa will be referred to herein as a trunk network connection point (“TNCP”); it will be understood that this term is to be construed broadly as a connection point to any external network and is not limited to connection to a conventional trunk network. Special nodes, referred to in the specific description herein as mesh insertion points (“MIPs”), will typically be placed by the network operator and will have an additional direct link (typically using any technology) to a TNCP. The process of mesh formation in such cases will normally need to ensure that all nodes in the mesh are connected (directly, or indirectly via other nodes) to a MIP. The process should also preferably ensure that adequate capacity is provided for all the data traffic to be routed, taking into consideration the capacities of all links (using any technology) as far as the TNCP. In an alternative case or in only some parts of the network, a MIP and TNCP may be the same device, in which case the process of mesh formation remains the same as described herein.
According to a first aspect of the present invention, there is provided a method of forming a network of nodes from a plurality of nodes and a plurality of potential transmission links between respective nodes, at least one of the nodes being a connection node that provides a data connection into and out of the formed network, and wherein for each node that is not a connection node there is a maximum number of links acceptable for a transmission path from said node to a connection node, each node in the formed network being able to communicate with at least one other node by a transmission link between said each node and said at least one other node, each of the nodes in the formed network other than said connection node or connection nodes being linked to at least one connection node by at least one transmission path that comprises either a single transmission link between the node and a connection node or respective transmission links between the node and a connection node via one or more intermediate nodes, the method comprising the steps of:
for a node which is not a connection node and which has not been linked to a connection node:                (a) where there is a single connection node, identifying all transmission paths from said node to said single connection node that do not exceed said maximum number of links or, where there are plural connection nodes, identifying all transmission paths from said node to any of said connection nodes that do not exceed said maximum number of links;        (b) testing said paths against at least one criterion for acceptability until an acceptable path is found and providing links between the or each node on that acceptable path so that the or each node on that acceptable path is linked to a connection node by a transmission path which comprises either a single transmission link between the node and a connection node or respective transmission links between the node and a connection node via one or more intermediate nodes; and,        (c) repeating steps (a) and (b) for all nodes which are not connection nodes and which have not been linked to a connection node.        
According to a second aspect of the present invention, there is provided a method of providing a topology for a network of nodes and actual transmission links between nodes by determining which of a plurality of potential transmission links between the nodes should be made into actual transmission links between nodes, at least one node being a connection node that provides a data connection into and out of the formed network, and wherein for each node that is not a connection node there is a maximum number of links acceptable for a transmission path from said node to a connection node, each node in the formed network being in communication with at least one other node by a transmission link between said each node and said at least one other node, each of the nodes in the formed network other than said connection node or connection nodes being linked to at least one connection node by at least one transmission path which comprises either a single transmission link between the node and a connection node or respective transmission links between the node and a connection node via one or more intermediate nodes, the method comprising the steps of:
for a node which is not a connection node and which has not been linked to a connection node:                (a) where there is a single connection node, identifying all transmission paths from said node to said single connection node that do not exceed said maximum number of links or, where there are plural connection nodes, identifying all transmission paths from said node to any of said connection nodes that do not exceed said maximum number of links;        (b) testing said paths against at least one criterion for acceptability until an acceptable path is found and flagging in a computer database or data structure a variable representing the or each node on that acceptable path to indicate that said the or each node on that acceptable path is linked to a connection node; and,        (c) repeating steps (a) and (b) for all nodes which are not connection nodes and which have not been flagged as linked to a connection node;        
thereby to provide a dataset representing a topology for a network of the nodes and transmission links between the nodes.
These first and second aspects allow formation of an access network that includes the nodes. There is provided a method which enables an operator to determine, in a finite and practically short time, how to link nodes to provide a desired degree of service to the nodes. In a typical embodiment, the result of the method will be a database or data structure that indicates or represents a topology showing for all nodes that can be connected into a mesh how they should be linked to other nodes. A network operator in practice can then take that database or data structure and implement a physical realisation of the mesh as generally described above and in our WO-A-98/27694 by linking actual nodes using actual transmission links in reliance on the topology indicated or represented by that database or data structure.
In either aspect, each of the transmission links may be a wireless transmission link. Alternatively, some of the transmission links may be wireless transmission links and the remainder of the transmission links are cabled transmission links. It will be understood that “cabled” is to be construed broadly to include any suitable tangible medium including for example wired connections, optical fibres, etc.
In either aspect, steps (a) to (c) are preferably applied to nodes in descending order of expected data flow rate requirements for the nodes. Thus, in this embodiment, the nodes with the highest bandwidth requirements are connected first, thereby helping to minimise the bandwidth.hops or bandwidth.distance product across the network. On average, the largest amounts of data will have the shortest distance to travel to and from a connection node. The “data flow requirements” may be for example the committed source rate or committed sink rate or the sum thereof for the nodes, optionally including a fixed or variable overhead for network management traffic.
The method may comprise the step of, after step (a) and before step (b), determining an order of priority of said paths and wherein in step (b) said paths are tested for acceptability in said order of priority.
In the method, where at least some of the links are wireless transmission links, step (a) may comprise identifying all paths from said node to at least one connection node, and the order of priority of the paths may be determined in ascending order of the number of wireless transmission links in those paths. In this example, the nodes with the smallest number of wireless transmission links in a path to a connection node are connected first, again helping to minimise the bandwidth.hops or bandwidth.distance product across the network.
In the method, step (a) may comprise identifying all paths from said node to at least one connection node, and the order of priority of the paths may be determined in ascending order of the total currently committed data flow rate of the connection nodes to which said paths lead. In this example, the connection node that has the lowest currently committed data flow rate is preferred, it being understood that the committed data flow rate of a connection node increases as nodes are linked to it during repeated iterations of the method.
Where at least some of the links are wireless transmission links, the order of the paths may be determined in ascending order of the total physical length of the wireless transmission links within said paths. In this example, the path with the shortest total physical length of any wireless transmission links in the path is preferred.
The order of the paths may be determined in descending order of the number of links in a path that form at least a portion of a path that has previously been determined to be acceptable. In this example, when there are paths that have already been determined to be acceptable, there will be links on that path that are already committed to carrying data traffic. When determining the order of paths, it is preferred that the largest possible number of previously committed links be re-used, so as to minimise the total number of links used at this stage of the network formation.
In one preferred embodiment, the order of the paths is determined by applying these criteria in the following sequence: in ascending order of the number of wireless transmission links in those paths, in ascending order of the total currently committed data flow rate of the connection nodes to which said paths lead, in ascending order of the total physical length of any wireless transmission links in said paths, and in descending order of the number of links in a path that form at least a portion of a path that has previously been determined to be acceptable. In another embodiment, the order of the paths is determined by applying these criteria in the following sequence: in ascending order of the total physical length of any wireless transmission links in said paths, in ascending order of the total currently committed data flow rate of the connection nodes to which said paths lead, in ascending order of the number of wireless transmission links in those paths, and in descending order of the number of links in a path that form at least a portion of a path that has previously been determined to be acceptable.
In step (b) a path may be determined to be unacceptable if linking the or each node on that path to a connection node would exceed the maximum data traffic flow rate for that connection node.
In the formed mesh, transmissions to and from a connection node may take place during distinct timeslots, in which case it is preferred that in step (b) a path is determined to be unacceptable if linking the or each node on that path to a connection node would exceed the number of timeslots available at that connection node.
In the formed mesh, transmissions to and from a connection node may take place during distinct timeslots, in which case it is preferred that in step (b) a path is determined to be unacceptable if linking the or each node on that path to a connection node would exceed the number of timeslots available at any node on that path.
The or each node on a path being tested in step (b) may have plural antennas, each antenna being capable of providing a respective wireless transmission link with another node, in which case it is preferred that a path is determined to be unacceptable in step (b) if linking the or each node on that path to a connection node would result in any of the nodes not having at least one free antenna. In this example, a path is rejected if it would result in any of the nodes on that path not having a free antenna. It is desirable for each node to have a free antenna which is not committed for use in normal operation of the network in order to allow actual signal or interference measurements to be made. Furthermore, having a free antenna enables verification that each line-of-sight proposed for use in the preferred “adaptation” steps discussed further below is viable for use as a radio link. Having a free antenna also enables or at least simplifies verification that a link will operate correctly after an adaptation sequence has been effected. Furthermore, a free antenna enables adaptation of a mesh without interruption to traffic flows.
The or each node on a path being tested in step (b) may have plural antennas, each antenna being capable of providing a respective wireless transmission link with another node, in which case it is preferred that step (b) comprises the further step of flagging all potential links to/from a node as unavailable for use in a path if that node is linked to a connection node and has only one free antenna or if that node is a connection node and has only one free antenna. This example prevents the method investigating the assignment of links to nodes which it is already known are not viable or preferred.
Step (b) may comprise the further step of flagging all potential links between two nodes as unavailable for use in a path if both of said nodes are linked to a connection node. This example removes from consideration links between nodes which are no longer suitable because redundant paths are not allowed in this embodiment or at this stage of the method.
Step (b) may comprise the further step of flagging all potential links between a node and a connection node as unavailable for use in a path if said node is linked to a connection node. This example again removes from consideration links between nodes which are no longer suitable because redundant paths are not allowed in this embodiment or at this stage of the method.
It is preferred that prior to linking a node to a connection node, a check is made of all other nodes that have not been linked to a connection node to determine whether any of said other nodes would be made unconnectable to a connection node if said first node were linked to said connection node. It is preferred that said first node is not linked to a connection node if there are any nodes that would be made unconnectable to a connection node if said first node were linked to said connection node.
The method may comprise the step of, prior to step (a), for a node that has a single potential link to another node, linking that node to another node using said single potential link and marking said single potential link as unavailable for use in another path. This is part of what is termed herein the “anti-orphan” procedure and prevents such nodes from being “orphaned” or cut off from the rest of the mesh.
The method may comprise the step of providing further links between at least some of the nodes so as to create redundant paths to a connection node for at least one of the nodes. In this preferred embodiment, redundant paths are added, preferably as far as possible so that as many nodes as possible have completely independent paths to the connection node in order to provide for resilience (in the sense that back-up paths are available in the event of the failure of any component in the primary path) and to provide for diversity (such that for example a large amount of data from one node can be divided into smaller amounts which are sent over different paths).
According to a third aspect of the present invention, there is provided a method of forming a network of nodes from a plurality of nodes and a plurality of potential transmission links between respective nodes, each node in the formed network being able to communicate with at least one other node by a transmission link between said each node and said at least one other node, each of the nodes in the formed network being linked to at least one designated anchor node by at least one transmission path that comprises either a single transmission link between the node and a designated anchor node or respective transmission links between the node and a designated anchor node via one or more intermediate nodes, wherein all nodes in the formed network are linked to all other nodes, and wherein for each node that is not a designated anchor node there is a maximum number of links acceptable for a transmission path from said node to a designated anchor node, the method comprising the steps of:
for a node which is not a designated anchor and which has not been linked to a designated anchor node:                (a) where there is a single designated anchor node, identifying all transmission paths from said node to said single designated anchor node that do not exceed said maximum number of links or, where there are plural designated anchor nodes, identifying all transmission paths from said node to any of said designated anchor nodes that do not exceed said maximum number of links;        (b) testing said paths against at least one criterion for acceptability until an acceptable path is found and providing links between the or each node on that acceptable path so that the or each node on that acceptable path is linked to a designated anchor node by a transmission path which comprises either a single transmission link between the node and a designated anchor node or respective transmission links between the node and a designated anchor node via one or more intermediate nodes; and,        (c) repeating steps (a) and (b) for all nodes which are not designated anchor nodes and which have not been linked to a designated anchor node.        
According to a fourth aspect of the present invention, there is provided a method of providing a topology for a network of nodes and actual transmission links between nodes by determining which of a plurality of potential transmission links between the nodes should be made into actual transmission links between nodes, each node in the formed network being in communication with at least one other node by a transmission link between said each node and said at least one other node, each of the nodes in the formed network being linked to at least one designated anchor node by at least one transmission path which comprises either a single transmission link between the node and a designated anchor node or respective transmission links between the node and a designated anchor node via one or more intermediate nodes, wherein all nodes in the formed network are linked to all other nodes, and wherein for each node that is not a designated anchor node there is a maximum number of links acceptable for a transmission path from said node to a designated anchor node, the method comprising the steps of:
for a node which is not a designated anchor node and which has not been linked to a designated anchor node:                (a) where there is a single designated anchor node, identifying all transmission paths from said node to said single designated anchor node that do not exceed said maximum number of links or, where there are plural designated anchor nodes, identifying all transmission paths from said node to any of said designated anchor nodes that do not exceed said maximum number of links;        (b) testing said paths against at least one criterion for acceptability until an acceptable path is found and flagging in a computer database or data structure a variable representing the or each node on that acceptable path to indicate that said the or each node on that acceptable path is linked to a designated anchor node; and,        (c) repeating steps (a) and (b) for all nodes which are not designated anchor nodes and which have not been flagged as linked to a designated anchor node;        
thereby to provide a dataset representing a topology for a network of the nodes and transmission links between the nodes in which all nodes in the formed network are linked to all other nodes.
These third and fourth aspects allow formation of a self-contained or “non-access” network that includes the nodes and rely on analogous steps as for formation of an access network as described above in connection with the first and second aspects. If there is one anchor node, then these methods produce a fully interconnected set of nodes. In the case of more than one anchor node, then a fully interconnected set of nodes will be produced if the anchor nodes are themselves interconnected. This may be done by any means, before or after the application of the method. It may be done by applying the method described herein to a set of lines-of-sight between the anchor nodes.
Preferred embodiments and detailed examples of these third and fourth aspects are generally analogous to those set out above for the first and second aspects described above.
According to another aspect of the present invention there is provided a computer program comprising program instructions for causing a computer to perform the method as described above.
According to yet another aspect of the present invention, there is provided a storage medium having stored thereon or therein a computer program as described above.
The storage medium may be a computer memory. The storage medium may be a read-only storage medium. Suitable read-only storage media include a CD-ROM or a semiconductor ROM. The storage medium may be a rewritable storage medium. Suitable rewritable storage media include a hard or floppy magnetic disk and a rewritable CD.
According to a yet further aspect of the present invention, there is provided a computer programmed to carry out the method as described above.
It will be understood that the term “computer” is to be construed broadly. The term “a computer” may include several distributed discrete computing devices or components thereof.
In many radio systems, the radio transmission method divides the transmissions into one or more slots, such as a repeating pattern of timeslots in a TDD system, as briefly referred to above in relation to one of the preferred embodiments of the method of formation. Furthermore, a radio node with multiple antennas may be designed such that each timeslot can be used at most once for transmission or reception purposes within the whole node. The preferred formation method discussed further below calculates meshes that are compatible with such constraints by ensuring that each node is required to use no more than the total available number of timeslots.
The preferred method of formation allows a number of goals to be set for it, according to the requirements that an operator wishes to impose on the network. These include:
1. providing the capacity to carry specified levels of traffic required to provide services to or between various nodes in the mesh;
2. providing back-up paths for such traffic so as to avoid interruption of such services in the event of the failure of a mesh link or node; and,
3. restricting the positions of certain nodes within the overall mesh topology.
An example of the third item mentioned above concerns nodes that are to be installed, de-installed or disrupted for maintenance purposes. The preferred formation method allows these nodes to be positioned in the mesh such that traffic to other nodes is not disrupted if these nodes are not operational. Thus, the preferred formation method can be operated to ensure that other traffic can be carried by the mesh before installation, after de-installation or during maintenance.
The meshes that are formed by the preferred method have the following components:
1. a set of radio links, or cabled links, or a combination of radio and cabled links, between nodes;
2. for each of the radio links, the number of timeslots required in each direction; and,
3. a set of traffic paths across the mesh, one or more per service according to the goals set for the formation method.
The process of formation thus addresses the calculation of a mesh that will achieve one or more goals that are set for it.
Providing for Peak Traffic Load
According to another aspect of the present invention, there is provided a method of forming a network of nodes from a plurality of nodes and a plurality of potential transmission links between respective nodes, each node in the formed network being able to communicate with at least one other node by a transmission link between said each node and said at least one other node, wherein at least one of the nodes has a peak traffic rate requirement for traffic to another point in the network and said node has a primary traffic path to said point in the network, the method comprising the steps of:
determining the traffic capacity of said primary path;
identifying other paths, other than said primary path, from said node to said point in the network such that the sum of the traffic capacity of said primary path and the traffic capacity of said other paths is equal to or greater than said peak traffic rate requirement for said node; and,
making said other paths available to carry traffic from said node to said point in the network in addition to said primary path;
whereby in the formed network if the traffic rate for traffic from said node to said point in the network exceeds the traffic capacity of said primary path, the traffic can be divided into discrete portions which are respectively delivered over the primary path and said other paths to said point in the network.
This method allows a peak traffic rate to be offered to a subscriber. It will be understood that, in practice, the peak traffic rate can be offered at some times, but that these times will depend entirely on other subscriber traffic levels and on any incidences of failed equipment or links in the network. The preferred method makes use of what is referred to herein as “inverse multiplexing” which is a process in which a single stream of data that must be sent from A to B is divided at A into discrete portions, each portion is transmitted along one of the plural (i.e. primary and other) paths, and the portions are joined together at B to recreate the original stream.
According to another aspect of the present invention, there is provided a method of forming a network of nodes from a plurality of nodes and a plurality of potential transmission links between respective nodes, each node in the formed network being able to communicate with at least one other node by a transmission link between said each node and said at least one other node, wherein at least one of the nodes has a peak traffic rate requirement for traffic to another point in the network and each said node has a primary traffic path plus zero or more other paths to each said point in the network, the method comprising the steps of:
determining the traffic capacity of each said path; and,
adding in a prioritised order capacity to links in the network such as provide for the peak traffic requirements at said nodes.
This provides an alternative or additional method for allowing a peak traffic rate to be offered to a subscriber.
Concatenation
According to another aspect of the present invention, there is provided a mesh communications network, the network comprising plural nodes and transmission links between the nodes, and wherein timeslots are allocated to the transmission links for transmission and reception of signals between the nodes over the links, wherein on at least one link at least two consecutive timeslots are allocated for transmission such that user traffic is in use transmitted continuously over more than one timeslot on said at least one link.
As discussed in more detail below, consecutive timeslots can be combined on a wireless transmission link where two or more timeslots are required in the same direction on that link such that additional capacity is provided on that link or such that the number of timeslots required on that link can be reduced.
Preferably, all timeslots have the same duration.
Colouring
“Colouring” is a term used herein to refer to the process of assigning timeslot numbers to each timeslot on a link in the mesh. This term is used herein because of the analogies that can be made with graph theory. It will be recalled that in the preferred implementation of the mesh, time is divided into discrete timeslots that are numbered within a time frame. For example, a wireless transmission on one wireless transmission link from a first node to another node may take place during timeslot 1; a wireless transmission on another wireless transmission link from that first node to a different other node may take place during subsequent timeslot 2; reception of a wireless transmission at the first node from another node may take place during timeslot 3; and so on. In what follows, the term “colours” is used to refer to these timeslot numbers such that different timeslots in a time frame are notionally associated with a different “colour”. Given that at any particular node it is desired to avoid having reception from or transmission to other nodes taking place during the same timeslot numbers (i.e. it is preferred that any particular node is only either transmitting to or receiving from one other node only at any time instant), each link to and from the node in this embodiment must have a different timeslot number or “colour”. (This assumes that all transmissions and receptions take place at the same carrier frequency. A discussion of the more general case, in which different frequency channels may be used, is given below.) Thus, the problem of allocating timeslots to the links on the nodes is analogous to the known problem of colouring of a graph in graph theory.
Colouring is the subject of copending patent application no. U.S. patent application Ser. No. 09/971,622 (US 2002/0044537 A1), which is assigned to the assignee of the present application.
In that copending patent application, there is disclosed a method of assigning timeslot numbers to timeslots used for transmission and reception of signals between nodes in a network of nodes in which each node is able to communicate with at least one other node by a transmission link between said each node and said at least one other node, at least some of the nodes having a respective transmission link to each of plural other nodes, each transmission of a signal over a link from a first node to a second node taking place during a timeslot, the method comprising the steps of:
assigning timeslot numbers to each timeslot in sequence in ascending order of the number of available choices of timeslot number at each timeslot.
In that copending patent application, there is also disclosed a method of assigning timeslot numbers to timeslots used for transmission and reception of signals between nodes in a network of nodes in which each node is able to communicate with at least one other node by a transmission link between said each node and said at least one other node, at least some of the nodes having a respective transmission link to each of plural other nodes, each transmission of a signal over a link from a first node to a second node taking place during a timeslot, the method comprising the steps of:                (a) identifying the node which has the greatest total number of timeslots to be used for transmission or reception of signals;        (b) for the node identified in step (a), assigning a different timeslot number to each of said timeslots at that node;        (c) determining which of the timeslots that have not yet been assigned a timeslot number has the least available choices of timeslot number and assigning a timeslot number to that timeslot so determined; and,        (d) repeating step (c) until all timeslots have been assigned a timeslot number.        
In step (a) of this aspect, if there are plural nodes having the same total number of timeslots to be used for transmission or reception of signals, then any of those nodes may be selected.
In step (b) of this aspect, the timeslot numbers may be assigned arbitrarily.
In that copending patent application, there is also disclosed a method of assigning timeslot numbers to timeslots used for transmission and reception of signals between nodes in a network of nodes in which each node is able to communicate with at least one other node by a transmission link between said each node and said at least one other node, at least some of the nodes having a respective transmission link to each of plural other nodes, each transmission of a signal over a link from a first node to a second node taking place during a timeslot, the method comprising the steps of:                (a) for each timeslot, setting a variable to have a value that is equal to twice the maximum number of timeslots numbers available;        (b) identifying the node which has the greatest total number of timeslots to be used for transmission or reception of signals;        (c) for the node identified in step (b), assigning a different timeslot number to each of said timeslots at that node;        (d) for each other timeslot sharing a node with the timeslots to which timeslots were assigned in step (c), reducing the value of the variable by a constant for each instance of said sharing of a node;        (e) selecting the timeslot having the smallest value of the variable;        (f) for each other timeslot sharing a node with the timeslot selected in step (e), reducing the value of the variable by a constant for each instance of said sharing of a node;        (g) repeating steps (e) and (f) until all timeslots have been selected; and,        (h) in order of the selection made in steps (e) to (g), assigning a timeslot number to each of the timeslots selected in steps (e) to (g).        
In step (b) of this aspect, if there are plural nodes having the same total number of timeslots to be used for transmission or reception of signals, then any of those nodes may be selected.
In step (c) of this aspect, the timeslot numbers may be assigned arbitrarily.
In any of these aspects, the timeslot number that is assigned to a timeslot is preferably the first timeslot number which is free at the nodes at both ends of the timeslot.
A timeslot number may be determined to be available taking into account interference that might arise in use on one link as a result of transmission on another link.
When assigning a timeslot number to a timeslot, an attempt to reduce interference effects can be made for example by (i) choosing the least-used timeslot number or (ii) choosing the most-used timeslot number or (iii) choosing the timeslot number which reduces the options for the smallest number of timeslots yet to be assigned timeslot numbers.
The method may comprise the step of assigning a frequency channel to each timeslot at which wireless transmission takes place during the timeslot. This can also be used as a way of reducing inter-node interference. The frequency that is assigned may for example be the frequency that has been least used or the frequency that has been most used.
The frequency channel assigned to the or each timeslot on at least one link may be selected taking into account interference that might in use be caused to or arise from a transmission/reception device that is not a part of said network of nodes during transmission over said at least one link. Thus, the interference effects which might otherwise arise both to and from another (“alien”) transmission/reception device can be accounted for before the mesh network is operated, thereby to prevent such interference occurring.
The available frequency channels are preferably ordered in descending order of the number of links from one node to another node for which interference to or from a transmission/reception device that is not a part of said network of nodes during transmissions would be unacceptable, and wherein the frequency channel assigned to the or each timeslot on said at least one link is the first acceptable frequency channel in said order.
The determination of whether or not a frequency channel is acceptable preferably takes into account interference that might in use be caused to or arise from a transmission/reception device that is not a part of said network of nodes during transmissions at the frequency channel.
On at least one link, at least two consecutive timeslots may be allocated for transmission such that user traffic is in use transmitted continuously over more than one timeslot on said at least one link. A timeslot number is preferably assigned to said at least one link before timeslot numbers are assigned to any link not having two consecutive timeslots allocated for transmission.
All timeslots preferably have the same duration.
Adaptation
When a mesh network is operational, in practice it is likely that a new mesh configuration will be required, typically when the goals or parameters set for the mesh are altered. Examples are when a node is to be added to or removed from the network; when the traffic requirements of an existing subscriber change; when an operator of the network decides to add or remove seed or other nodes; when two nodes become no longer visible to each other (perhaps because trees have grown or buildings have been erected between the two nodes); when the current mesh topology becomes sub-optimal or falls below some quality threshold; when a wireless or other transmission link is added or removed between two existing nodes; when a timeslot on a wireless transmission link between two existing nodes is added, removed or reallocated; when main or back-up paths for existing subscriber traffic are reconfigured; and any combination of these events.
In principle, the new mesh configuration could be obtained by effectively forming the new mesh “from scratch”, i.e. using a formation method to form the new mesh that meets the new requirements and without any regard to the configuration of the current mesh. The current mesh could then be made inoperative for a period in order for the new mesh to be constructed. However, such an operation would not in general be commercially acceptable owing to the temporary loss of service that would be experienced by the current users. An alternative operation could effectively be by “trial and error” in which the operator would for example try to add a new node in an ad hoc way simply by actually adding the new node and attempting to assign it links and timeslots, etc. and then testing the new mesh to determine whether the new mesh configuration operates successfully. However, such an approach is on average very unlikely to be successful given the interdependence of the nodes on each other across the mesh to obtain successful operation, including especially their link and timeslot assignments, etc.
Thus, in practice, a process is likely to be required to alter one mesh configuration to another mesh configuration in a controlled and predictable way. The term “mesh adaptation” or similar is used herein to refer generally to the process required to alter one mesh configuration to another mesh configuration in this manner. A mesh adaptation should preferably be carried out such that the mesh retains its ability to carry the data traffic of all subscribers throughout the adaptation process.
The problem of mesh adaptation, like that of mesh formation, will normally be a mathematically hard problem given the enormous number of potential links that will exist given a typical set of (unconnected) nodes and the fact that the number of combinations of potential communication links increases much more rapidly than the number of nodes. Moreover, as noted above, not all topologically valid meshes will be suitable for use as a mesh network because of practical problems, such as for example the presence of a limited number of antennas available at each node, data traffic capacity limitations at each node or of the available RF spectrum (including a limitation on the number of timeslots available for transmission and reception), and restrictions on the length of traffic paths between the nodes (measured both in physical lengths of individual links and the number of transit nodes through which data passes from a source node to a target node). In the case of adaptation, the problems are in practice exacerbated by the preferred objective that the adaptation be carried out such that the mesh retains its ability to carry the data traffic of all subscribers throughout the adaptation process.
Thus, according to another aspect of the present invention, there is provided a method of adapting an initial mesh communications network configuration to a final mesh communications network communications configuration, wherein:
the initial mesh communications network configuration comprises a first set of nodes, transmission links between the nodes, timeslot allocations to the transmission links and traffic paths across the mesh;
the final mesh communications network configuration comprises a second set of nodes, transmission links between the nodes, timeslot allocations to the transmission links and traffic paths across the mesh;
the first set of nodes, transmission links between the nodes, timeslot allocations to the transmission links and traffic paths across the mesh being different to the second set of nodes, transmission links between the nodes, timeslot allocations to the transmission links and traffic paths across the mesh; and,
wherein there exists a method of forming a mesh communications network configuration from a set of nodes and potential transmission links between the nodes and which allocates timeslots to the transmission links;
the method comprising the step of forming at least a part of the final mesh communications network configuration by operating the method of forming a mesh either or both (i) on the basis of a restricted set of the potential transmission links between the nodes of the second set thus constraining the results produced by the mesh formation such that the initial mesh configuration can be adapted to the final mesh configuration and (ii) by adding one or more additional steps or tests to the method of forming a mesh that constrain the results produced by the mesh formation such that the initial mesh configuration can be adapted to the final mesh configuration.
The first set may differ from the second set in terms of one or more of the nodes (i.e. whether they are present or not), the transmission links between the nodes, timeslot allocations to the transmission links and traffic paths across the mesh. The first set may additionally or alternatively differ from the second set in terms of other factors, including for example the goals that they are required to achieve, examples of such goals being given above.
In an embodiment, the initial mesh communications network configuration has an initial primary topology being a non-redundant set of paths from every node of the first set to a connection node of the first set, and the final mesh communications network configuration has a final primary topology being a non-redundant set of paths from every node of the second set to a connection node of the second set, and wherein there is at least one new node in the final mesh communications network configuration that is not in the initial mesh communications network configuration,
the step of forming at least part of the final mesh communications network configuration preferably comprising operating the method of forming a mesh on a restricted set of the potential transmission links between the nodes of the second set to produce a final primary topology which is the same as the initial primary topology plus at least one transmission link to the or each new node and in which the or each new node is configured as a node which is at the end of a primary path and which is not configured to be a transit node within the final primary topology for traffic intended for other nodes. Thus, in this embodiment, no changes are made to the existing primary topology and hence no changes are made to the existing primary traffic paths of existing traffic services; no transmission links are used in the new mesh that were not included in the current mesh, except for transmission links where at least one end of each link is at a new node. Thus, each new node is configured as a “leaf”. This embodiment encompasses the adaptation methods referred to herein as “provisioning”.
Said restricted set of the potential transmission links between the nodes of the second set may be the combination of all primary topology transmission links in the initial mesh communications network configuration plus all potential transmission links between the or each new node and a node in the initial mesh network configuration, whereby the final primary topology is the same as the initial primary topology plus at least one transmission link to the or each new node. This embodiment provides one way of ensuring that the final primary topology is the same as the initial primary topology plus at least one transmission link to the or each new node, as required for the class of adaptation referred to herein as “provisioning”. In general, provisioning requires the least changes to be made to the mesh and is therefore the easiest to achieve and in general should be tried first although, on average, it is the method that is least likely to succeed.
In an embodiment, the initial mesh communications network configuration has an initial primary topology being a non-redundant set of paths from every node of the first set to a connection node of the first set, and the step of forming the final mesh communications network configuration being constrained to prevent a primary path being added that adds a timeslot to any transmission link in the initial primary topology or requires a timeslot to be removed from any transmission link. This corresponds to what, in the preferred embodiment, is referred to herein as “strict provisioning” in which the entire current mesh, without any modifications to it, forms a part of the new mesh. No changes to the current mesh need to be made which affect existing mesh links or paths for existing services. The only changes to the mesh required in a practical implementation consist of adding or removing nodes, links to them, and services and traffic paths to them as a part of an installation/deinstallation procedure.
In another embodiment, the initial mesh communications network configuration has an initial primary topology being a non-redundant set of paths from every node of the first set to a connection node of the first set, wherein in the step of forming the final mesh communications network configuration, one or more timeslots are added to links in the initial primary topology. This corresponds to what, in the preferred embodiment, is referred to herein as “additive provisioning”. In the preferred embodiment, timeslots are added to existing links provided that this can be done without changing the configurations of timeslots already in use on any of the links in the current mesh.
In another embodiment, the initial mesh communications network configuration has an initial primary topology being a non-redundant set of paths from every node of the first set to a connection node of the first set, wherein the step of forming the final mesh communications network configuration includes the step of removing one or more links which are in the initial mesh communications network configuration and which are not in the initial primary topology. This corresponds to what, in the preferred embodiment, is referred to herein as “subtractive provisioning” in which “resilience links” (i.e. those not in the primary topology and which are used to provide for alternative, back-up paths for traffic as discussed further below) may be removed as required in order to make way for a new link in the primary topology.
In another embodiment, the initial mesh communications network configuration has an initial primary topology being a non-redundant set of paths from every node of the first set to a connection node of the first set, and the final mesh communications network configuration has a final primary topology being a non-redundant set of paths from every node of the second set to a connection node of the second set, and wherein there may be at least one new node in the final mesh communications network configuration which is not in the initial mesh communications network configuration, and
in the step of forming at least part of the final mesh communications network configuration, said restricted set of the potential transmission links between the nodes of the second set is preferably all transmission links in the initial mesh network configuration plus, where there is at least one new node in the final mesh communications network configuration that is not in the initial mesh communications network configuration, all potential transmission links between the or each new node and a node in the initial mesh communications network configuration. This embodiment corresponds to the class of adaptation referred to herein as “redistribution”. In the preferred implementation of these methods, no transmission links are used in the new mesh that were not included in the current mesh, except, where there is at least one new node in the final mesh communications network configuration that is not in the initial mesh communications network configuration, for transmission links where at least one end of each link is at a new node. However, no other restrictions are imposed, so that the new primary topology can use any existing links in the mesh. Links from the current mesh may not necessarily appear in the new mesh. These methods can be used for example where one or more new nodes are to be installed into an existing mesh. These methods are also suitable as a way to adjust the primary topology so that specified nodes become leaves or where the overall parameters of the mesh require to be adjusted.
Preferably, the change from the initial mesh communications network configuration to the final mesh communications network configuration is made as a single triggered step.
According to another aspect of the present invention, there is provided a method of adapting an initial mesh communications network configuration to a final mesh communications network communications configuration, wherein:
the initial mesh communications network configuration comprises a first set of nodes, transmission links between the nodes, timeslot allocations to the transmission links, and traffic paths across the mesh;
the final mesh communications network configuration comprises a second set of nodes, transmission links between the nodes, timeslot allocations to the transmission links, and traffic paths across the mesh;
the first set of nodes, transmission links between the nodes, timeslot allocations to the transmission links and traffic paths across the mesh being different to the second set of nodes, transmission links between the nodes, timeslot allocations to the transmission links and traffic paths across the mesh;
the initial mesh communications network configuration having an initial primary topology being a non-redundant set of paths from every node of the first set to a connection node of the first set, and the final mesh communications network configuration having a final primary topology being a non-redundant set of paths from every node of the second set to a connection node of the second set;
wherein there exists a method of forming a primary topology for a mesh communications network configuration from a set of nodes and potential transmission links between the nodes and which allocates timeslots to the transmission links;
the method comprising the step of operating the method of forming a mesh to form the final primary topology such that it can co-exist with the initial primary topology, whereby the initial mesh configuration can be adapted to the final mesh configuration.
This aspect of the present invention corresponds to the class of adaptation referred to herein as “methods of coexisting primaries”. In the preferred implementation of these methods, a new mesh is produced in which new transmission links are added between existing nodes. Thus, in these methods, some antenna movements are typically required within the existing mesh. These methods preferably constrain the formation process to produce a new mesh such that only one or two groups of antenna movements are required and such that the change steps involve operating only one intermediate mesh. The methods attempt to find a new mesh such that all antennas required for the old primary topology and the new primary topology can be allocated at the same time. Hence, the antenna positions required for the primary topology of the new mesh can be achieved without prejudice to the ability of the current primary topology to carry all committed traffic across the mesh.
Preferably, in the method of forming the final primary topology, a path is determined to be unacceptable if at any node on the path, the number of potential transmission links that would be used for the path and that were not links in the initial primary topology exceeds the number of new links that the node can support in the final topology as calculated on the basis of the number of timeslots and antennas at the node left free while operating the links of the initial primary topology.
According to a further aspect of the present invention, there is provided a method of adapting an initial mesh communications network configuration to a final mesh communications network communications configuration, wherein:
the initial mesh communications network configuration comprises a first set of nodes, transmission links between the nodes, timeslot allocations to the transmission links, and traffic paths across the mesh;
the final mesh communications network configuration comprises a second set of nodes, transmission links between the nodes, timeslot allocations to the transmission links, and traffic paths across the mesh;
the first set of nodes, transmission links between the nodes, timeslot allocations to the transmission links and traffic paths across the mesh being different to the second set of nodes, transmission links between the nodes, timeslot allocations to the transmission links and traffic paths across the mesh;
the initial mesh communications network configuration having an initial primary topology being a non-redundant set of paths from every node of the first set to a connection node of the first set, and the final mesh communications network configuration having a final primary topology being a non-redundant set of paths from every node of the second set to a connection node of the second set;
wherein there exists a method of forming a primary topology for a mesh communications network configuration from a set of nodes and potential transmission links between the nodes and which allocates timeslots to the transmission links;
the method comprising the steps of:
(A) operating the method of forming a mesh to form an intermediate primary topology such that it can co-exist with the initial primary topology,
(B) operating the method of forming a mesh to form a further intermediate primary topology which can co-exist with the previous intermediate topology,
(C) repeating step (B) until the further intermediate primary topology can co-exist with the final primary topology,
whereby the initial mesh configuration can be adapted to the final mesh configuration via a sequence of co-existing primary topologies.
This aspect of the present invention corresponds to what is referred to herein as “repeated overlapping primaries”. In general, this is the most likely method to succeed of the methods of adaptation described herein though it is likely to require the most changes, and is therefore the most disruptive, and is the most computationally intensive.
In an embodiment, the adaptation process is preceded by use of the formation process to produce a target mesh that achieves its goals. The adaptation process then starts from either the target or the current mesh and then applies a modified version of the formation process, where the modifications are such as to calculate one or more intermediate meshes. A corresponding number of change steps can then be carried out in practice to transform the current mesh to the target mesh. It will be understood that the calculation of the intermediate mesh(es) can be carried out starting from either the current mesh or the target mesh because the or each intermediate mesh must have a primary topology that can co-exist with the primary topology of its adjacent meshes in the change sequence.
Most preferably, in the methods of adaptation referred to above, said method of formation is a method as described in general terms above and in greater detail below. The actual embodiment of the method of formation that is required to be used in any particular method of adaptation will depend on the requirements for the adaptation process itself and on the nature of the initial and final mesh communications network configurations. Thus, the actual method of formation used in practice in a method of adaptation may use one or more of the variants to the method of formation discussed in detail herein.
In summary therefore, in accordance generally with these aspects of the present invention, a method of adaptation can in principle make use of any method that is used to form a mesh of the type described above, with that formation method being appropriately constrained when used as part of the adaptation method. Preferably, the formation method of which the adaptation method makes use provides the capabilities described above, namely: 1. providing the capacity to carry specified levels of traffic required to provide services to or between various nodes in the mesh; 2. providing back-up paths for such traffic so as to avoid interruption of such services in the event of the failure of a mesh link or node; and, 3. restricting the positions of certain nodes within the overall mesh topology.
Thus, in general terms, a preferred embodiment of this aspect of the present invention provides a method of adaptation in which a formation method is modified to produce a mesh that not only meets its new goals but that also can be reached in a sequence of one or more change steps from the currently operating mesh and such that, at each change step in the sequence, the mesh retains its ability to carry the data traffic of all subscribers throughout the adaptation process. A new mesh is thus produced by the adaptation process which meets the goals set for it and which can be reached in a sequence of one or more change steps from the currently operating mesh.
Preferably, the modifications applied to the formation method fall into one or both of the following categories:
1. the set of links from which the formation process is permitted to choose various components of the new mesh is restricted at one or more stages of the formation process, the restricted set(s) being chosen such as to ensure that the new mesh can be reached in a sequence of one or more change steps from the currently operating mesh; and,
2. one or more additional restrictions or tests are added at one or more stages of the formation process, the result of such restrictions or tests being to ensure that the new mesh can be reached in a sequence of one or more change steps from the currently operating mesh.
It will be understood that where the adaptation process requires restriction of the set of links from which the formation process is permitted to choose various components of the new mesh, then different restricted sets may be used at different stages of the formation process.
There are many adaptation methods consisting of different sets of modifications that can be applied to a formation process in order to produce a valid change step sequence for adaptation. In other words, in general, plural differing sequences of changes will be viable in order to adapt from an initial mesh configuration to a final mesh configuration, and those different sequences of changes can be obtained by applying different sets of modifications to a formation process. The sequences of changes making up the adaptation processes will differ in a number of ways. Some of the important characteristics of an adaptation sequence in a practical implementation will include:    1. the set of change steps that are assumed to be possible. The set of change steps that are possible depends on the specification of the networking equipment from which the mesh is constructed. This specification can be chosen in such a way as to give rise to particular methods. Elements of specification that are preferably provided in combination with the adaptation methods described herein are set out below.    2. the number of change steps that are produced.    3. the time required to carry out each change step.    4. the characteristics of the mesh during these steps.    5. the characteristics of the final mesh.    6. the set of possible failures in the networking equipment that might prevent the sequence from being carried out correctly and the probability of these failure occurring. An example of a failure that may prevent an adaptation sequence being carried out correctly would be the failure of a remotely controlled steerable antenna to move to a new required position. An adaptation method would be vulnerable to such a failure only if it required repositioning of one or more antennas.
These above mentioned factors will affect the reliability of operation of the mesh during and after adaptation and hence the overall reliability of the network. For example, the characteristics of the mesh during an intermediate step might include a much lower level of back-up capability than is the case of the initial or final mesh. An equipment or radio link failure at that step would therefore carry a high risk of service disruption. Since the final meshes produced by different methods may also vary in their levels of back-up capability, the long term ability of the mesh to minimise service disruption also depends on the method used. There are many other characteristics that will vary between the meshes produced by different methods, such as their ability to handle peak traffic loads.    7. the probability that an adaptation sequence exists according to the method. Each adaptation method potentially applies different constraints on the choices available to the mesh formation process and thus affects the probability that a solution can be produced by the method.
For each method, the resulting adaptation sequence can be evaluated against one or more of the above criteria. By combining this with the operational requirements of a specific network, the most appropriate method can be selected.
A common operational requirement is that each adaptation is carried out such as to minimise the risk that the steps will fail to complete correctly. For example, if antenna repositioning were found to be a particularly unreliable process, then a method with the smallest number of repositioning operations might be preferred.
The different examples of the adaptation methods described herein in general differ in the probability that they will produce a successful adaptation sequence. In the preferred implementation, these methods can be ordered in an ordering such that as this probability increases, both the complexity and the length of the adaptation sequence increases and also the time required to calculate a valid sequence increases. Therefore, in one preferred implementation, the adaptation sequence is calculated by trying the methods in ascending order of probability that they produce a solution (i.e. trying first the method that is least likely to succeed) and/or the complexity of the adaptation method, until one method produces a solution.
Accordingly, in accordance with another aspect of the present invention, there is provided a method of adapting an initial mesh communications network configuration to a final mesh communications network communications configuration, wherein:
the initial mesh communications network configuration comprises a first set of nodes, transmission links between the nodes, timeslot allocations to the transmission links and traffic paths across the mesh;
the final mesh communications network configuration comprises a second set of nodes, transmission links between the nodes, timeslot allocations to the transmission links and traffic paths across the mesh;
the first set of nodes, transmission links between the nodes, timeslot allocations to the transmission links and traffic paths across the mesh being different to the second set of nodes, transmission links between the nodes, timeslot allocations to the transmission links and traffic paths across the mesh; and, wherein there exists a set of adaptation techniques available for adapting the initial mesh communications network configuration to the final mesh communications network communications configuration which can be ordered in ascending order of likelihood of success of the adaptation and/or complexity of execution;
the method comprising the step of applying said set of adaptation techniques in said ascending order until one of said techniques is successful in adapting the initial mesh communications network configuration to the final mesh communications network communications configuration.
Preload and Trigger Functions
Preferably, at least some of the changes to the initial mesh communications network configuration that are required as part of the adaptation to the final mesh communications network configuration form a group of changes such that all of the changes within the group can occur substantially simultaneously, the method comprising the step of executing a group of such changes by:
transmitting relevant information about the changes in the group to each node that during the adaptation will take part in any of the changes of said group; and,
subsequently transmitting an instruction to each said node to carry out said changes of said group, thereby to cause each said node to effect said changes of said group substantially simultaneously.
In another aspect of the present invention, there is provided a method of adapting an initial mesh communications network configuration to a final mesh communications network communications configuration, wherein:
the initial mesh communications network configuration comprises a first set of nodes, transmission links between the nodes, timeslot allocations to the transmission links, and traffic paths across the mesh;
the final mesh communications network configuration comprises a second set of nodes, transmission links between the nodes, timeslot allocations to the transmission links, and traffic paths across the mesh;
the first set of nodes, transmission links between the nodes, timeslot allocations to the transmission links and traffic paths across the mesh being different to the second set of nodes, transmission links between the nodes, timeslot allocations to the transmission links and traffic paths across the mesh;
wherein at least some of the changes to the initial mesh communications network configuration that are required as part of the adaptation to the final mesh communications network configuration form a group of changes such that all of the changes within the group can occur substantially simultaneously, the method comprising the step of executing a group of such changes by:
transmitting relevant information about the changes in the group to each node that during the adaptation will take part in any of the changes of said group; and,
subsequently transmitting an instruction to each said node to carry out said changes of said group, thereby to cause each said node to effect said changes of said group substantially simultaneously.
Preferably, where there are plural groups of said changes, the information transmitting step comprises the step of transmitting relevant information about the changes of all groups to each node which during the adaptation will take part in any of the changes.
Preferably, the method comprises the step of, after a predetermined time following the instruction transmitting step, interrogating each said node to determine if the change has occurred successfully.
As will be discussed further below, an adaptation from an initial mesh configuration to a final mesh configuration is preferably carried out as one or more change steps. Plural networking equipment devices can preferably carry out plural such operations simultaneously. The time taken to carry out such steps will typically affect the overall reliability of the network. It is thus in general beneficial to carry out an adaptation using a small number of steps, to minimise the time taken for each step and to maximise the probability that each step is commanded successfully. As discussed above, the commanding of change steps is preferably carried out by a “preload and trigger” sequence, a specific example of which is described in detail below.
Management Connectivity
In order to operate the mesh in practice, there will normally be connectivity between each of the mesh nodes and one or more management systems. In general, this connectivity is required in order that the state of the network can be monitored from one or more control centres. In general, such connectivity would also be used in order to configure and reconfigure the nodes. In the context of adaptation discussed above, this connectivity can be used to send adaptation instructions from the mesh change controller to the nodes and to monitor the success of each adaptation change step. It is highly desirable that the management connectivity be able to make use of any possible path from the control centre to any node: for example, provided there is management connectivity, this can be used to restore non-management or user traffic connectivity. Maximum possible management connectivity is important when a series of adaptation steps is being carried out. This allows faults that occur during an adaptation to be detected and corrective actions to be caused to take place at the relevant nodes. However, the duration of an adaptation is a difficult period in which to ensure continued management connectivity, due to the changes to the network topology that are occurring.
According to another aspect of the present invention, there is provided a mesh communications network, the network comprising plural nodes and transmission links between the nodes arranged in a network topology, at least some of the nodes being linked to plural other nodes via transmission links, each of said at least some nodes having a routing table for routing signals across the network by specifying the link along which signals from the node to another node are to be sent and being capable of updating the routing table according to the status of links in the network, each of said at least some nodes being arranged such that for certain predetermined changes to the network topology the updated routing table is not applied immediately for routing signals across the network.
Preferably, each of said at least some nodes is adapted to enter into a split table mode for said certain predetermined changes to the network topology by which the routing table that was in use prior to said certain predetermined changes to the network topology taking place continues to be used for routing signals across the network whilst a separate updated routing table is calculated and stored separately, the updated routing table being used to route signals across the network after split table mode is exited.
Said certain predetermined changes may include one or more of failure or restoration or creation of a link or modification of the desirability of a link. In this context, “desirability” can be related to what is referred to in the description below as the “cost” of a link.
According to another aspect of the present invention, there is provided a method of measuring the behaviour of a proposed mesh communications network whilst operating an existing mesh communications network, wherein:
the proposed mesh communications network comprises a proposed network of nodes in which each node is able to communicate with at least one other node by a wireless transmission link between said each node and said at least one other node, each transmission of a signal over a link from a first node to a second node taking place during a timeslot; and wherein:
the existing mesh communications network comprises an existing network of nodes in which each node is able to communicate with at least one other node by a wireless transmission link between said each node and said at least one other node, each transmission of a signal over a link from a first node to a second node taking place during a timeslot;
the method comprising the steps of:
using one or more auxiliary timeslots within the existing mesh communications network to emulate the wireless transmission environment of one or more proposed transmission configurations over the links that will exist in the proposed mesh communications network.
This method may be used for example during installation of a new node to verify that it will operate compatibly with the existing mesh. As another example, when a change to a new link and colouring arrangement is about to happen, then the auxiliary timeslots can be used to verify that this new arrangement is compatible across the mesh, while still operating the previous link and colouring arrangement. The new arrangement can be tested out for each normal timeslot in turn.